{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "xhTvbO2tb5fR"
   },
   "source": [
    "## Search Exercise 2\n",
    "\n",
    "# Defining a Search Problem and using a General Search Algorithm\n",
    "\n",
    "## The Jug Pouring Puzzle Example\n",
    "\n",
    "#### Last edit: 10am, Tuesday 1st Feb 2022\n",
    "\n",
    "This Python notebook will introduce you to a simple software tool that will enable you to define search problems and attempt to find solutions using a variety of different algorithms parameters.\n",
    "\n",
    "## Learning Objectives\n",
    "\n",
    "Studying and experimenting with this notebook should help you to acquire the following knowledge and skills:\n",
    "\n",
    "* Understanding of the general structure and components of a search problem.\n",
    "\n",
    "* Understanding of how a real problem can be specified in this form.\n",
    "\n",
    "* Appreciation of how features of a particular search problem can affect the performance of search algorithms and how this varies depending on the algorithm.\n",
    "\n",
    "* Ability to experiment with applying a variety of algorithms to a problem.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "bpIRCuXrNEiw"
   },
   "source": [
    "## Using this Jupyter/Colab Notebook\n",
    "\n",
    "This module does not involve fully-fledged programming assignments. However, we will be exploring AI topics using some software tools and code examples, that you will need to read through and modify in various ways in order to develop your understanding.\n",
    "\n",
    "_Notebook_ programs are a convenient way to combine formated explanatory material and code within a single file. For Python, the Jupyter notebook interface is  very popular. It is based on the _Iron Python NoteBook_ files format (file extension `.ipynb`). These files can also be run on the cloud using services such as Google Colab.\n",
    "\n",
    "### Quickstart use of the notebook\n",
    "\n",
    "If you are looking at this for the first time then you will be seeing it in the Colab programming interface.\n",
    "You can simply proceed by reading each section and following the instructions to run the _code cells_ that are interleaved with the textual information.\n",
    "\n",
    "### Futher use of this and other notebook files\n",
    "\n",
    "After you have gone through this file and experimented with what it can do you should find out a bit more about Python Notebook files and how to use them. I have put information about his on a\n",
    "web page: [PythonNotebookInfo](https://teaching.bb-ai.net/AI-2611/PythonNotebookInfo.html). That page has links to a lot of further information which some of you may find useful. For this course you only need a basic understanding of Python and Notebook files, so looking at the extra stuff is optional; but it does include a couple of introductory videos that you might find useful."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "T1fdPQ2JErwZ"
   },
   "source": [
    "## Brandon's Generic Search Algorithm\n",
    "\n",
    "The best way to learn about how to employ AI search algorithms on actual problems is to try it yourself, starting with some simple cases. \n",
    "To do this you can use my Python implementation of a general search algorith implemented in a very similar way to what Russell and Norvig describe.\n",
    "\n",
    "When you run the following code cell it should download the my Python module from the web and install it locally. This should work on pretty much any Python platform. Obviously you will need internet access, but once it has been installed you could run the rest of the notebook off line.\n",
    "\n",
    "### Running a code cell\n",
    "The following chunk of code is a _code cell_. It is actually a sequence of Linux commands that get down my code file from the web and save it on the file system of whatever system is running this file (can either be a cloud system like Colab, or your local machiine). Most code cells are Python code but in this case we are using the `!` at the beginning of the line, which enables operating system shell commands to be executed.\n",
    "\n",
    "To run the code cell in Colab you click the run symbol (white triangle on a black circle) that will appear in the top left of the cell when you move your mouse over it. **Do that now.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "id": "Xjm-PwqMNEi0"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Installing bbSearch module from web ...\n",
      "creating bbmodcache subfolder\n",
      "downloading bbSearch module\n",
      "  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current\n",
      "                                 Dload  Upload   Total   Spent    Left  Speed\n",
      "100 18767  100 18767    0     0  11429      0  0:00:01  0:00:01 --:--:-- 11422\n"
     ]
    }
   ],
   "source": [
    "!echo Installing bbSearch module from web ...\n",
    "!echo creating bbmodcache subfolder\n",
    "!mkdir -p bbmodcache\n",
    "!echo downloading bbSearch module\n",
    "!curl http://bb-ai.net.s3.amazonaws.com/bb-python-modules/bbSearch.py > bbmodcache/bbSearch.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "tF9FJg42NEi1"
   },
   "source": [
    "### Now you should be able to `import` from the `bbSearch` module\n",
    "Now try running the follwing cell. Click the run symbol (or you can use `<shift>+<enter>` as a keyboard shortcut):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "Yqnek7KVNEi3"
   },
   "outputs": [],
   "source": [
    "from bbmodcache.bbSearch import SearchProblem, search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "JSta0v1cNEi4"
   },
   "source": [
    "The bbSearch Python module should now be loded which will enable us to use the `SearchProblem` class and the `search` function. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "H54fzf_JNEi5"
   },
   "source": [
    "## The SearchProblem Class\n",
    "\n",
    "Below is the code that defines the `SearchProblem` class in `bbSearch`. This is\n",
    "for viewing not editing. It is just a copy of what is in the actual `bbSearch` module.\n",
    "This class definition is essentially a template for defining search problems. It is a _base class_ that\n",
    "needs to be _extended_ to define an actual search problem, as we shall see shortly below.\n",
    "Hence most of the method definitions are just place holders with comments describing what they\n",
    "should do. But please **read the following code carefully**, paying particular attention to the functions:\n",
    "`__init__`, `possible_actions`, `successor` and `goal_state`.\n",
    "\n",
    "```python\n",
    "class SearchProblem:\n",
    "\n",
    "    def __init__( self ):\n",
    "        \"\"\"\n",
    "        The __init__ method must set the initial state for the search.\n",
    "        Arguments could be added to __init__ and used to configure the\n",
    "        initial state and/or other aspects of a problem instance.\n",
    "        \"\"\"\n",
    "        self.initial_state = None ## Change this to set the actual initial state!\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def info(self):\n",
    "        \"\"\"\n",
    "        This function is called when the search is stared and should\n",
    "        print out useful information about the problem.\n",
    "        \"\"\"\n",
    "        print(\"This is the general SearchProblem parent class\")\n",
    "        print(\"You must extend this class to encode a particular search problem.\")\n",
    "\n",
    "    def possible_actions(self, state):\n",
    "        \"\"\"\n",
    "        This takes a state as argument and must return a list of actions.\n",
    "        Both states and actions can be any kinds of python data type (e.g.\n",
    "        numbers, strings, tuples or complex objects of any class).\n",
    "        \"\"\"\n",
    "        return []\n",
    "\n",
    "    def successor(self, state, action):\n",
    "        \"\"\"\n",
    "        This takes a state and an action and returns the new state resulting\n",
    "        from doing that action in that state. You can assume that the given \n",
    "        action is in the list of 'possible_actions' for that state. \n",
    "        \"\"\"\n",
    "        return state\n",
    "\n",
    "    def goal_test(self, state):\n",
    "        \"\"\"\n",
    "        This method should return True or False given any state. It should return \n",
    "        True for all and only those states that are considert \"goal\" states.\n",
    "        \"\"\"\n",
    "        return False\n",
    "    \n",
    "    def cost(self, path, state):\n",
    "        \"\"\"\n",
    "        This is an optional method that you only need to define if you are using\n",
    "        a cost based algorithm such as \"uniform cost\" or \"A*\". It should return\n",
    "        the cost of reaching a given state via a given path.\n",
    "        If this is not defined, it will is assumed that each action costs one unit\n",
    "        of effort to perform, so it returns the length of the path.\n",
    "        \"\"\"\n",
    "        return len(path)\n",
    "    \n",
    "    def heuristic(self, state):\n",
    "        \"\"\"\n",
    "        This is an optional method that should return a heuristic value for any\n",
    "        state. The value should be an estimate of the remaining cost that will be\n",
    "        required to reach a goal. For an \"admissible\" heuristic, the value should\n",
    "        always be equal to or less than the actual cost.\n",
    "        \"\"\"\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def display_action(self, action):\n",
    "        \"\"\"\n",
    "        You can set the way an action will be displayed in outputs.\n",
    "        \"\"\"\n",
    "        print(action)\n",
    "\n",
    "    def display_state(self, state):\n",
    "        \"\"\"\n",
    "        You can set the way a state will be displayed in outputs.\n",
    "        \"\"\"\n",
    "        print(state)\n",
    "        \n",
    "    def display_state_path( self, actions ):\n",
    "        \"\"\"\n",
    "        This defines output of a solution path when a list of actions\n",
    "        is applied to the initial state. It assumes it is a valid path\n",
    "        with all actions being possible in the preceeding state.\n",
    "        You probably don't need to override this.\n",
    "        \"\"\"\n",
    "        s = self.initial_state\n",
    "        self.display_state(s)\n",
    "        for a in actions:\n",
    "            self.display_action(a)\n",
    "            s = self.successor(s,a)\n",
    "            self.display_state(s)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ggSxesJ4N_vS"
   },
   "source": [
    "## A Simple Search Example: Jug Pouring Puzzle\n",
    "\n",
    "Many simple examples are provided by types of problem that we consider to be *puzzles*. Although puzzles are primarily considers as amusements, the problems involved in solving them are of the same general form those that arise in serious practical problems. Solving such problems can certainly certainly make life easer and in some cases can be very profitable or even save lives.\n",
    "But puzzles are often simpler and clearer in terms of the exact details of what is the problem and what solition is required.\n",
    "\n",
    "A typical and quite well know type of puzzle is the\n",
    "**Jug Pouring Puzzle** (or water pouring puzzle). There are many versions of this, but the basic idea is that we have some containers that can measure certain definite quantities of liquid and we want to measure some other quantity by transfering the liquid between the containers by a sequence of pouring actions. In order to ensure accuracy of the measurement, we are only allowed to carry out the following kinds of pouring action:\n",
    "\n",
    "* Pour liquid from a source jug to a receiving jug until either:\n",
    "    * the receiving jug becomes full (whatever cannot fit remains in the source jug);\n",
    "    * or, all liquid from the source jug is transferred into the receiving jug (so the source becomes empty).\n",
    "\n",
    "You can consult Wikipedia for further explanation: [Wikipedia: Water Pouring Puzzle](https://en.wikipedia.org/wiki/Water_pouring_puzzle).\n",
    "An example of this kind of problem is the [\"Die Hard 3\" Problem](https://www.math.tamu.edu/~dallen/hollywood/diehard/diehard.htm), which featured in the _Die Hard 3_ movie.\n",
    "(In the movie, they have two empty jugs that they can fill from a fountain. But you can model the fountain as a container that is much bigger than the jugs.)\n",
    "For a theoretical consideration you could take a look at the paper [_Measuring with Jugs_ (Boldi, Santini, Vigna, 2002)](https://www.sciencedirect.com/science/article/pii/S0304397501000603), but you will see that the hard-core mathematical treadment of this kind of problem is extremely complex.\n",
    "\n",
    "### Jug Pouring Puzzle state representation\n",
    "\n",
    "To model this kind of puzzle as a search puzzle, we need to decide upon a suitable representation of a state.\n",
    "There are countless possibilities of how we can do this. Some will be more convenient or computationally efficient than others. A simple idea that works well in Python is to use a dictionry where we have a key for each of the jugs whose value is a tuple giving the maximum capacity of the jug and its current contents.\n",
    "So this is an example state:\n",
    "```\n",
    "    {\"small\":(3,1), \"medium\":(5,0), \"large\":  (8,8) }\n",
    "```\n",
    "Here the \"small\" jug has capacity 3 units and contains 1 unit of liquid, the \"medium\" jug has capacity 5 units and is empty and the \"large\" jug has capacity 8 and is full.\n",
    "\n",
    "### `JugPouringPuzzle` Class definition\n",
    "\n",
    "The following class definition specified `JugPouringPuzzle` as and extension\n",
    "of `SearchProblem`. It fills in the specific details of the methods of\n",
    "the template class `SearchProblem`.\n",
    "\n",
    "You should read the code carefully to get a good understanding of how to model a search problem. The code in each of the methods is not especially complex. It is the combination of the methods and how they are used in the search algorithm that creates a very powerful algorithm.\n",
    "\n",
    "One thing that you should note is the use of the `deepcopy` function within the `successor` method, which  the starting point for creating the next state.\n",
    "The effect of `deepcopy(x)` is to return an object that is identical to the object\n",
    "referred to by `x`, except that it is a different object. This means that we can then modify the copy without changing the original object from which it was derived. This is essential in the `successor` function because if there are several actions possible from a given state we may need to generate several successors of that state. So we don't want the successor function to alter it. Forgetting this is a common error in writing search algorithms and can be very hard to debug if you are not aware of this kind of issue.\n",
    "\n",
    "Apart from that, the rest of the code is just quite simple tests and operations on the\n",
    "dictionary datastructure we have specified to represent the state of the jugs.\n",
    "\n",
    "The following chunk of code defining `JugPouringPuzzle` is in an editable and runable Python code cell, so you could edit it to modify the class definition. But for the time being you should not alter it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "ZtyKqVsAUS1P"
   },
   "outputs": [],
   "source": [
    "from copy import deepcopy\n",
    "\n",
    "class JugPouringPuzzle( SearchProblem ):\n",
    "    \n",
    "    def __init__( self, initial_state, goal_quantity ):\n",
    "        \"\"\"\n",
    "        Initialise a JugPouringPuzzle instance by setting the initial state\n",
    "        and the goal quantity.\n",
    "        \"\"\"\n",
    "        self.initial_state = initial_state\n",
    "        self.goal_quantity = goal_quantity\n",
    "        print( \"Creating SearchProblem object\" )\n",
    "        print( \"Setting initial state to:\", self.initial_state )\n",
    "        print( \"Goal quantity to measure:\", self.goal_quantity )\n",
    "        \n",
    "        self.jugs = self.initial_state.keys()\n",
    "\n",
    "    def info(self):\n",
    "        print( \"Measuring Jugs problem:\" )\n",
    "        print( \"You have a number of jugs with a certain volume and initial contents, as follows:\")\n",
    "        for jar in self.initial_state:\n",
    "          print(f\"{jar:>10} : volume={self.initial_state[jar][0]}, \"\n",
    "                          f\"contents={self.initial_state[jar][1]}\")\n",
    "        print( \"The goal quantity is:\", self.goal_quantity)\n",
    "\n",
    "    def possible_actions(self, state):\n",
    "        \"\"\"\n",
    "        Possible actions are to pour liquid from one jug to another. These are represented by:\n",
    "        (j1, j2), where j1 is the source jug and j2 is the receiver.\n",
    "        j1 cannot be empty and j2 cannot be full.\n",
    "        \"\"\"\n",
    "        actions = [] # start with empty action list\n",
    "        for j1 in self.jugs:\n",
    "            for j2 in self.jugs:\n",
    "                if ( j1!=j2  #different jugs\n",
    "                     and state[j1][1] > 0  # j1 not empty\n",
    "                     and state[j2][0] > state[j2][1] # j2 not full\n",
    "                   ): actions.append((j1,j2)) # action possible, add to actions list\n",
    "        return actions\n",
    "                    \n",
    "    def successor(self, state, action):\n",
    "        \"\"\"\n",
    "        Give the state resulting from given state when an action (j1,j2) is formed.\n",
    "        \"\"\"\n",
    "        \n",
    "        ## We need to construct a new state.\n",
    "        ## First make a copy of the original state.\n",
    "        ## Note don't directly change the given state as the algorithm may need to\n",
    "        ## construct other copies of it resulting from different possible actions\n",
    "        ## Assign new_state to a deep copy of state:\n",
    "        new_state = deepcopy(state)\n",
    "        \n",
    "        # The acion specifies two jugs j1 and j2\n",
    "        j1, j2 = action[0], action[1]\n",
    "\n",
    "        # Get contents of the jugs and space left in receiving jug\n",
    "        vol_in_j1 = state[j1][1]                    \n",
    "        vol_in_j2 = state[j2][1]\n",
    "        space_in_j2 = state[j2][0] - state[j2][1]  \n",
    "        \n",
    "        if vol_in_j1 <= space_in_j2:     # Case where all j1 contents can go into j2\n",
    "            new_j1 = 0\n",
    "            new_j2 = vol_in_j1 + vol_in_j2\n",
    "        else:                                 # Case where only some can be transfered\n",
    "            new_j1 = vol_in_j1 - space_in_j2  # Fill the space taking from j1\n",
    "            new_j2 = state[j2][0]             # j2 will now be full\n",
    "        \n",
    "        ## Now add the new values for each jug to the new state dictionary\n",
    "        ## (The capacity (first number) stays the same, just contents of j1 and j2 changes)\n",
    "        new_state[j1] = (state[j1][0], new_j1)  \n",
    "        new_state[j2] = (state[j2][0], new_j2)\n",
    "        return new_state\n",
    "\n",
    "    def goal_test(self, state):\n",
    "        \"\"\"\n",
    "        Test whether the state is a goal state.\n",
    "        This is when the content of one of the jugs is the same as the goal quantity.\n",
    "        \"\"\"\n",
    "        quantities = [ state[k][1] for k in state]\n",
    "        return  self.goal_quantity in quantities\n",
    "\n",
    "    def display_action( self, action ):\n",
    "        \"\"\"\n",
    "        Display an action in an easy to understand way.\n",
    "        \"\"\"\n",
    "        j1, j2 = action\n",
    "        print(f\"Pour from {j1} to {j2}:\")\n",
    "\n",
    "    def display_state( self, state ):\n",
    "        \"Display a state in a nice way.\"\n",
    "        jug_quantities = [ f\"{k} ({state[k][0]}): {state[k][1]}\" for k in state]\n",
    "        print( \", \".join(jug_quantities))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "yWZlMOhSNEi9"
   },
   "source": [
    "####  Run `JugPoruingPuzzle` class definition code cell\n",
    "Once you have read through the above code cell you should run it to execute the class definition (press the triangle in circle symbol at top left of the cell)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Cmre1EOrTiRr"
   },
   "source": [
    "### Create a `JugPouringPuzzle` instance\n",
    "It is now very easy to define a specific jug pouring puzzle as an instance of the\n",
    "`JugPouringPuzzle` classe. For example, the following code creates a puzzle instance where we have empty small and medium jugs withe capacities 3 and 8 and a full large jug with capacity 8. The goal is to measure 4 units of liquid. <br>\n",
    "By now you should recognise that the following is a code cell and know how to run it.<br>\n",
    "**In the rest of this notebook and in following exercises I will not remind you about running the code cells. You should always do that.**\n",
    "\n",
    "**Note:** If you forgot to run one of the previous cells you will get an error. Usually the code cells of a notebook need to be run from top to bottom in order for them to work. If you get an error such as `'xyz' is not defined` this means you probably missed one and need to go back and run previous cells. In Colab you will see a green tick mark on the left of a cell after it has been run."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "NLk7q6XaSe1-"
   },
   "outputs": [],
   "source": [
    "JPP_1 = JugPouringPuzzle( \n",
    "           {\"small\":(3,0), \"medium\":(5,0), \"large\":  (8,8) }, #initial state\n",
    "           4   # goal measurement\n",
    "        )                 \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "V-sjQTt_Qi9A"
   },
   "source": [
    "## The `search` function \n",
    "We can now call the search function itself. This takes 3 required paremeters and some optional arguments:\n",
    "\n",
    "* A `SearchProblem` object (for example an instance of the `JugsSearchProblem` that we have just defined.\n",
    "\n",
    "* A chosen **search type** which can be one of:\n",
    "    * `'BF/FIFO'`  Breadth-First search (uses a First in First out __queue__ to store generated states waiting to be tested).\n",
    "    * `'DF/LIFO'`  Depth-First (uses a Last In First Out __stack__ to store generated                        states waiting to be tested).\n",
    "                   \n",
    "\n",
    "* A **node limit** (an `int`), which is the maximum number of nodes that will be created in the search tree before the search is aborted. (Note that each node corresponds to a state, but states can potentially occur at many nodes as there could be many ways to get to the same state.)\n",
    "\n",
    "* Optional arguments:\n",
    "    * `loop_check` You can have this on or off by adding `loop_check=True` or `loop_check=False`. The default value is `False`.\n",
    "    * `randomise`  (`=True` or `=False`, default `False`).\n",
    "       If this is set to true, the list of possible actions will be shuffled\n",
    "       into a random order before they are inserted into the search queue.\n",
    "       (If cost and heuristic functions are set they will still be used to\n",
    "        determine position of insertion in the queue so will only make a\n",
    "        difference for states whose cost and/or heuristic values are tied.)\n",
    "    * `show_path`  (`=True` or `=False`, default `True`), \n",
    "      choose whether to output the action path found by the search.\n",
    "    * `show_state_path`  (`=True` or `=False`, default `False`), \n",
    "       choose whether to output the sequence of states found by the search.\n",
    "    * `return_info`  (`=True` or `=False`, default `False`), \n",
    "      If `True` the `search` function will return a dictionary giving full details of the \n",
    "      search that was carried out and the result obtained. If `False` the function will\n",
    "      just return a string describing whether the search was successful."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "cA0x60YCN8dK"
   },
   "outputs": [],
   "source": [
    "search( JPP_1, 'BF/FIFO', 2000, loop_check=False, randomise=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Jlkn00uGNEi_"
   },
   "source": [
    "## Changing the Initial and Goal states\n",
    "\n",
    "The `JugPouringPuzzle` class can \n",
    "\n",
    "Here is a very simple case. I want to measure 3 units of water. \n",
    "I have an empty mug an empty kettle and a sink half full of water.\n",
    "So the initial state is:\n",
    "```python\n",
    "   {'mug':(1,0), 'kettle':(6,0), 'sink':(40,20)},\n",
    "```\n",
    "\n",
    "Or perhaps I have a large barrel of beer and want to transfer 20 pints\n",
    "into a flagon, but I only have a huge tankard and a jug to transfer the\n",
    "precious liqud. We can represent the initial state as:\n",
    "\n",
    "```python\n",
    "   {'tankard':(5,0), 'jug':(7,0), 'barrel':(80,75), 'flagon':(40,19)}\n",
    "    \n",
    "```\n",
    "\n",
    "So let us try the example with the mug and kettle. It seems pretty simple.\n",
    "Depth-first search is offten more efficient, so we could try using that\n",
    "instead of bread-first. So we put the search mode as 'DF/FIFO' (i.e. Depth First implemented using a First In First Out _heap_ data structure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "xNHoiIlHNEjA"
   },
   "outputs": [],
   "source": [
    "JPP_2 = JugPouringPuzzle( \n",
    "            {'mug':(1,0), 'kettle':(6,0), 'sink':(40,20)},\n",
    "            3\n",
    "         ) \n",
    "\n",
    "search( JPP_2, 'DF/LIFO', 10000, \n",
    "        loop_check=False, randomise=False, show_state_path=True )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "N1QCgbu8Erwc"
   },
   "source": [
    "* Did that work? \n",
    "* What could go wrong with such a simple example? \n",
    "* Maybe you could try changing some of the options."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "dr6VNeW1NEjA"
   },
   "source": [
    "## JugPouringPuzzle Search Exercise\n",
    "\n",
    "### Required Tasks\n",
    "\n",
    "To achieve the learning objectives of this Search exercise, you should address\n",
    "all of the following tasks and questions:\n",
    "\n",
    "1. Experiment with all the parameters of the search algorithm.\n",
    "\n",
    "2. Try to create a hard jug pouring problem of your own. Can you create one with a very long solution path (e.g. 10 or more pourings required)? \n",
    "\n",
    "3. What affect does adding extra containers that are not useful have on the search algorithm? For instance, what if I modify the initial state of `JPP_1` to add 4 more empty containers with capacity 3 and 3 full containers with capacity 20. How does this alter the effectiveness with which the algorithms can solve the problem? (**Note:** you need to make sure that each container has a different name in the state representation (a dictionary can only have one value of each key. If you use the same key several times, only the last will be stored in the dictionary)).\n",
    "\n",
    "4. Which type of search algorithm should you use to find the _minimum_ number of pourings required to solve a given pug pouring puzzle?\n",
    "\n",
    "4. Overall, what do you think is the best choice of parameters to give to the `search` function to solve jug pouring puzzles most effectively?\n",
    "\n",
    "### Optional Extra Investigation\n",
    "\n",
    "There are many ways you could extend this exercise to gain further insight into search algorithms.\n",
    "One idea would be to write another kind of search problem class\n",
    "which is a variant of `JugPouringPuzzle` and can solve a different or wider set of puzzles. For instance you could add actions for filling a jug from a tap or for pouring away the contents.\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [
    "N1QCgbu8Erwc"
   ],
   "name": "SearchExercise2.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
